/**
 * 描述：使用动态数组来实现最大堆
 *
 * @author WangB
 * 2018-10-22-0:34
 */
public class MaxHeap<E extends Comparable<E>>{

    private Array<E> data;//底层使用动态数组

    public MaxHeap(int capacity){
        data = new Array <> (capacity);
    }

    /**
     * 构造函数，这样之后，data数组已经存入了用户传来的
     * arr数组里面的数据了。
     * 这就是heapify的过程
     * 也就是找到最后一个非叶子节点。就等于，最后一个元素的父节点（完全二叉树）
     * @param arr
     */
    public MaxHeap(E[] arr){
        data = new Array <> (arr);
        for ( int i = parent (arr.length - 1) ; i >=0 ; i-- ) {
            siftDown (i);
        }
    }
//    @Override
//    public int compareTo(E e){
//        return this.data - e;
//    }

    public MaxHeap(){
        data = new Array <> ();
    }

    public int size(){
        return data.getSize ();
    }

    public boolean isEmpty(){
        return data.isEmpty ();
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点
     * 的索引
     * @param index
     * @return
     */
    private int parent(int index){
        if(index == 0 )
            throw  new IllegalArgumentException ("no son");
        return (index - 1)/2;
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的左儿子节点
     * 的索引
     * @param index
     * @return
     */
    private int leftChild(int index){
        return index*2 + 1;
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的右儿子节点
     * 的索引
     * @param index
     * @return
     */
    private int rightChild(int index){
        return index*2 + 2;
    }

    /**
     * 向堆中添加一个元素
     * @param e
     */
    public void add(E e){
        data.addLast (e);//将元素先添加到数组末端
        siftUp(data.getSize () -1);
    }

    /**
     * 上浮的过程，动态调整堆
     * @param k：希望上浮的元素对应的索引
     */
    private void siftUp(int k){
        while(k > 0 && data.get(parent (k)).compareTo (data.get (k))<0){
            //循环的条件就是1.k没有到达根节点。2.k比他爹的值大。
            data.swap (k,parent (k));//交换k和他爹两个元素
            k = parent (k);//当前k已经到了他爹的位置上去了。
        }
    }

    /**
     * 获取堆中的最大的元素
     * @return
     */
    public E findMax(){
        if(data.getSize ()==0)
            throw new IllegalArgumentException ("data is empty");
        return data.get (0);
    }

    /**
     * 从堆中取出最大元素
     * @return 堆中的最大值
     */
    public E extractMax(){
        E ret =findMax ();//找到堆的最大元素。
        data.swap (0,data.getSize () -1);//交换堆尾和最大的元素
        data.removeLast ();//堆中最大的那个元素就会被删除
        siftDown(0);
        return ret;
    }

    /**
     * 下沉的过程，动态调整堆
     * @param k 希望下沉的元素对应的索引
     */
    private void siftDown(int k){
        while (leftChild (k)<data.getSize ()){//k的左孩子的索引小于数组数的大小的时候
            int j  = leftChild (k);
            if(j+1<data.getSize () //说明有右孩子
                    && data.get (j + 1).compareTo (data.get (j))>0){
                j =rightChild (k);

            }
            if(data.get (k).compareTo (data.get (j)) >=0)
                break;

            data.swap (k,j);
            k = j ;

        }
    }

    /**
     * 取出堆中的最大元素，然后添加一个新的元素。
     * 可以采用先extract，再add，
     * 也可以直接将max返回，然后将待插入元素与之替换。
     * @param e
     * @return
     */
    public E replace(E e){
        E ret = findMax ();

        data.set (0,e);
        siftDown (0);
        return ret;
    }


}
